package com.agile.leetcode.tree.diameterOfBinaryTree;

/**
 * 二叉树的直径问题
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 *
 *  
 *
 * 示例 :
 * 给定二叉树
 *
 *           1
 *          / \
 *         2   3
 *        / \
 *       4   5
 * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author:ChenZhangKun
 * @Date: 2021/4/12 10:37
 */
public class DiameterOfBinaryTree {
    public static void main(String[] args) {
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(5);
        TreeNode node3=new TreeNode(3);
        TreeNode node2=new TreeNode(2,node4,node5);
        TreeNode node1=new TreeNode(1,node2,node3);
        DiameterOfBinaryTree diameterOfBinaryTree=new DiameterOfBinaryTree();
        System.out.println(diameterOfBinaryTree.diameterOfBinaryTree(node1));
    }
    public int diameterOfBinaryTree(TreeNode root) {
        if (root==null) return 0;
        dfs(root);
        return max;
    }
    int max=0;
    private int dfs(TreeNode root){
        // 叶子节点
        if (root.left==null&&root.right==null){
            return 0;
        }
        // 递归
        int leftSize=root.left==null?0:dfs(root.left)+1;
        int rightSize=root.right==null?0:dfs(root.right)+1;
        max=Math.max(max,rightSize+leftSize);
        return Math.max(leftSize,rightSize);

    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
